Cloud storage services, such as the popular class of “NoSQL” data stores, have been designed to meet the needs of diverse applications from social networking to electronic commerce. Such storage services replicate application data on multiple machines to make it highly available and to improve performance. Many provide a relaxed form of consistency, eventual consistency, in order to achieve elastic scalability and good performance while some strive for strong consistency to maintain the semantics of one-copy serializability. To allow local access and ensure data survivability even during a complete data center failure, many storage systems offer the option of replicating data across different regions of the world, called “geo-replication.”
With data being replicated on a world-wide scale, the inherent tradeoffs between performance and consistency are exaggerated due to the high communication latencies between data centers. The performance difference between reads with different consistencies can be substantial. Strongly consistent reads generally involve multiple replicas or are serviced by a primary site whereas eventually consistent reads can be answered by the closest replica. Even within a data center, the latency of strongly consistent reads has been measured as eight times that of reads with weaker session guarantees. With geo-replication, the performance differences can be more than two orders of magnitude.